//package work.rightAnswer;
//
//class minEditDistance_72 {
//    public int minDistance(String word1, String word2) {
//        char[] w1 = word1.toCharArray();
//        char[] w2 = word2.toCharArray();
//
//        int[][] dp = new int[w1.length+1][w2.length+1];
//        for (int i = 0; i <= w1.length; i++) {
//            dp[i][0] = i;
//        }
//        for (int i = 0; i <= w2.length; i++) {
//            dp[0][i] = i;
//        }
//
//        for (int i = 1; i <= w1.length; i++) {
//            for (int j = 1; j <= w2.length ; j++) {
//                int leftAdd = dp[i][j-1]+1;
//                int rightAdd = dp[i-1][j]+1;
//                int change = dp[i-1][j-1];
//                if(w1[i-1]!=w2[j-1]){
//                    change++;
//                }
//
//                dp[i][j] = Math.min(leftAdd,Math.min(rightAdd,change));
//            }
//        }
//
//        return dp[w1.length][w2.length];
//    }
//
//    //长度为index1的数组w1和长度为index2数组w2之间的最短编辑距离
//    public int minEditDistance(char[] w1,char[] w2,int index1,int index2){
//        if(index1==0){
//            return index2;
//        }
//        if(index2==0){
//            return index1;
//        }
//
//        if(w1[index1-1]==w2[index2-1]){
//            return Math.min(minEditDistance(w1,w2,index1-1,index2-1),
//                    Math.min(minEditDistance(w1,w2,index1-1,index2)+1,minEditDistance(w1,w2,index1,index2-1)+1));
//        }else {
//            return Math.min(minEditDistance(w1,w2,index1-1,index2-1)+1,
//                    Math.min(minEditDistance(w1,w2,index1-1,index2)+1,minEditDistance(w1,w2,index1,index2-1)+1));
//        }
//    }
//}